package com.sort;

import com.SortTestHelper;

import java.util.Arrays;

public class SortEx {
    public static void main(String[] args) {
        Integer[] integers1 = SortTestHelper.generateRandomArray(10000, 0, 10000);
        Integer[] integers2 = SortTestHelper.generateRandomArray(10000, 0, 10000);
        Integer[] integers3 = SortTestHelper.generateRandomArray(10000, 0, 10000);
        Integer[] integers4 = SortTestHelper.generateRandomArray(10000, 0, 10000);

        long begin1 = System.currentTimeMillis();
        bubbleSort(integers1);
        long end1 = System.currentTimeMillis();
        System.out.println(end1 - begin1);

        long begin2 = System.currentTimeMillis();
        selectSort(integers2);
        long end2 = System.currentTimeMillis();
        System.out.println(end2 - begin2);

        long begin3 = System.currentTimeMillis();
        insertSort(integers3);
        long end3 = System.currentTimeMillis();
        System.out.println(end3 - begin3);

        long begin4 = System.currentTimeMillis();
        quickSort(integers4);
        System.out.println(Arrays.toString(integers4));
        long end4 = System.currentTimeMillis();
        System.out.println(end4 - begin4);

    }

    public static void insertSort2(Comparable[] arr) {
        Comparable insertNode;
        int j;
        for (int i = 1; i < arr.length; i++) {
            insertNode = arr[i];
            j = i - 1;
            while (j >= 0 && insertNode.compareTo(arr[j]) == -1) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = insertNode;
        }
    }

    public static void insertSort(Comparable[] arr) {
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            //Comparable insertNode = arr[i];
            for (int j = i; j > 0; j--) {
                if (arr[j].compareTo(arr[j - 1]) == -1) {
                    Comparable temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else break;
            }
        }
    }

    /**
     * 选择排序
     * 定义一个 pos 锚点
     */
    public static void selectSort(Comparable[] arr) {
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            int pos = i;
            for (int j = i + 1; j < length; j++) {
                if (arr[pos].compareTo(arr[j]) == 1) {
                    pos = j;
                }
            }
            if (pos != i) {
                Comparable temp = arr[pos];
                arr[pos] = arr[i];
                arr[i] = temp;
            }
        }
    }

    /**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(Comparable[] arr) {
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            for (int j = 1; j < length - i; j++) {
                if (arr[j - 1].compareTo(arr[j]) == 1) {
                    Comparable temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     */
    public static void quickSort(Comparable[] arr) {
        quickSortImpl(arr, 0, arr.length - 1);
    }

    private static void quickSortImpl(Comparable[] arr, int start, int end) {
        if (start >= end) return;

        Comparable pivot = arr[start];
        int left = start;
        int right = end;
        while (left <= right) {
            while (left <= right && arr[left].compareTo(pivot) == -1) {
                left++;
            }
            while (left <= right && arr[right].compareTo(pivot) == 1) {
                right--;
            }

            if (left <= right){
                Comparable temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
        quickSortImpl(arr, start, right);
        quickSortImpl(arr, left, end);
    }
}
